package sort;

import java.util.Arrays;

/**
 * @Author: fzykd
 * Date: 2024-04-18
 * Time: 22:20
 * User: LQH
 */


//快速排序
public class QuickSort {

    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);

        System.out.println(Arrays.toString(array));

    }

    public static void quick(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(array, left, right);
        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }

    private static int partition(int[] array, int start, int end) {
        int tmp = array[start];
        while (start < end) {
            while (start < end && array[end] >= tmp) {
                end--;
            }
            //end 下标就遇到了 < tmp的值
            array[start] = array[end];
            while (start < end && array[start] <= tmp) {
                start++;
            }
            array[end] = array[start];

        }
        array[start] = tmp;
        return start;
    }

    public static void main(String[] args) {
        quickSort(new int[]{6, 3, 8, 4, 1, 7, 0, 9});
    }
}
